With the rapid development of data compression technologies, vector quantization has been widely used. Vector quantization (VQ) is an efficient data compression technique, which constructs a plurality of scalar data columns into a vector and performs overall quantization in the vector space. As a result, the data is compressed while no much information is lost. The procedure of VQ is as follows: each frame of k samples of a signal waveform or each parameter set of k parameters is constructed into a vector in a k-dimensional Euclidean space and the vector is then “collectively” quantized. When the vector is quantized, the k dimensional infinite space is divided into M regions with borders, and the input signal vector is compared with these borders and quantized to a central vector of a region whose borders have the minimum “distance” from the input signal vector. Computational complexity of VQ is mainly concerned with codebook searching according to a certain distortion measure criterion, and the spatial complexity is mainly determined by the size of the used codebook space. Generally, the larger the codebook space is, the larger the required storage is, and the higher the computational complexity of the codebook searching is, though the higher the quantization accuracy is.
Currently, the computational complexity of VQ is generally reduced by using multi-stage quantization or split codebook quantization. A procedure of a two-stage quantization is as shown in FIG. 1, in which an input vector x goes through a first stage VQ using codebook 1 and a second stage VQ using codebook 2. Though the codebook size of M1 and M2 are used in the two stages of VQ respectively, the resultant codebook effect is equivalent to a one-stage VQ having the size of M1*M2. Therefore, in contrast to the one-stage VQ system, the number of computations for distortion and comparison and the required storage of codebooks are respectively reduced from M1*M2 to M1+M2.
The split codebook quantization method is used to reduce the complexity in searching and storage when high-dimensional vectors are quantized. In this method, a vector to be quantized is split into two or more sub-vectors for quantization. An example of splitting the vector into two sub-vectors is described in the following. Assuming the input vector is x=[x1, x2, . . . , xN]T, the used codebook is Y, and the quantized bit length is L, then the storage space needed for storing the codebook Y is N×2L. If x is split into to sub-vectors xa=[x1, x2, . . . , xK]T and xb=[xK+1, xK+2, . . . , xN]T, then the used codebook is split into Ya and Yb accordingly. Assuming the quantized xa has a bit length of La and the quantized xb has a bit length of Lb, where L=La+Lb, the space needed for storing the codebook Ya is K×2La, and the space needed for storing the codebook Yb is (N−K)×2Lb, and thus the totally needed storage space is far less than the space N×2L needed for storing the codebook Y. In particular, when the dimensions of xa and xb are the same and the corresponding dimension components have similar statistical properties, i.e. Ya=Yb, more storage can be saved.
According to the voice coding standard “conjugate-structure algebraic-code-excited linear prediction voice encoder” by International Telecommunication Union (ITU), the signal spectrum parameter, i.e. Linear Spectrum Frequency (LSF), obtained after the Linear Prediction Coding (LPC) analysis is quantized by using a fourth order Moving Average (MA) model prediction quantizer to predict LSF coefficients of the current frame. The prediction error is quantized using a two-stage VQ. The first stage is to process a ten dimensional vector by using codebook L1 with 7 bit code. The second stage splits the ten dimensions into two 5-dimensional codebooks L2 and L3, where L2 represents the lower five dimensions and L3 represents the higher five dimensions, and both use 5 bit code.
However, according to the voice coding standard “silence compression solution of conjugate-structure algebraic-code-excited linear prediction voice encoder” by ITU, VQ of the LSF coefficients of the noise frame is done using a two-stage quantization. The input of the first stage quantizer is the prediction error of the predictor, and the quantization error from the first stage is quantized in the second stage. The first stage quantization codebook for the noise frame is a subset of the first stage codebook for the voice frame, and the second stage quantization codebook for the noise frame is a subset of the second stage codebook for the voice frame. That is, two sub-codebooks with the length of 16 bits may be trained from two codebooks with the length of 32 bits, which are both the second stage quantization codebooks, and codebook indices are saved in an array.
Conventional quantization has the following drawback:
When the computational complexity of the VQ procedure is reduced using the multi-stage quantization method, the codebooks for quantization at each stage are independent from each other and each codebook requires a corresponding codebook space. As a result, the storage space is wasted and the resource usage efficiency is low.